|
|
Parity vertex colorings
Soukup, Jan ; Gregor, Petr (vedoucí práce) ; Kučera, Petr (oponent)
Paritní cesta ve vrcholovém barvení grafu G je cesta ve které je každá barva použita sudě-krát. Paritní vrcholové barvení je barvení, které nemá žádnou paritní cestu. Nechť χp(G) je minimální počet barev v paritním bar- vení grafu G. Je známo, že χp(Bn) ≥ √ n, kde Bn je úplný binární strom s n vrstvami. Dokážeme, že platí ostrá nerovnost, a pomocí tohoto odhadu dokážeme nový odhad χp(T) > 3 √ log n, kde T je libovolný binární strom s n vrcholy. Dále se zabýváme časovou složitostí výpočtu paritního chromatického čísla χp(G). Dokážeme, že ověřování korektnosti paritního vrcholového bar- vení je coNP-úplné a popíšeme exponenciální algoritmus, který ho počítá. Dále pomocí Courcelleho věty dokážeme že existuje FPT algoritmus parame- trizovaný počtem barev k a stromovou šířkou grafu G ověřující že χp(G) ≤ k. Navíc popíšeme náš vlastní FPT algoritmus řešící tento problém. Tento al- goritmus běží v polynomiálním čase pro omezené k a stromovou šířku G. Na- konec zkoumáme příbuznost tohoto barvení s dalšími barveními, konkrétně s unique maximum, conflict free a parity edge barveními.
|
host ::
RSS.